/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/5/24.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * 这道题有一丢丢难度～嗨
 */
#include <string.h>
#include <stdio.h>

static char *longestPalindrome(char *s){
    int L = 0;
    int n = (int) strlen(s);
    int max_steps = 0, steps = 0;
    char find = 0, ok;
    register int i, j;
    register char *s2;
    for(i = 0; i < n - 1; ++i) {        /* 递推式检查字符串 */
        if(s + n - s < max_steps) break;    /* 没必要继续了 */
        s2 = s + i + 1;
        while (*s2) {                   /* 对这个字串进行检查 */
            steps++;                    /* 步数++ */
            /* 如果发现一个字符和首字母产生回文，并且步数超过以前确定的最大值，那么进入检查 */
            if(*s2 == *(s + i) && steps > max_steps) {
                ok = 1;     /* 我们假定它是一个回文串 */
//                printf("steps: %d\n", steps);
                if(steps > 1) {    /* 如果步数 > 1，需要继续判断，对于 <= 1 的，它肯定是 */
                    int mid = (steps + 1) >> 1;
                    for(j = 1; j < mid; ++j) {  /* 依次检查中间的前后字符，如果有不同的，则不是回文串 */
                        if(*(s + i + j) != *(s + i + steps - j)) {
                            ok = 0;
                            break;
                        }
                    }
                }
                if(ok) {    /* 如果是回文串，记录它 */
                    max_steps = steps;
                    L = i;
                    find = 1;
                }
            }
            s2++;
        }
        steps = 0;
    }
//    printf("max_steps: %d, find: %d, L: %d\n", max_steps, find, L);
    static char ans_buf[1024] = { 0 };
    if(find) {
        memcpy(ans_buf, s + L, max_steps + 1);
        ans_buf[max_steps + 1] = 0;
    } else {
        ans_buf[0] = *s;
        ans_buf[1] = 0;
    }
    return ans_buf;
}

int main(void) {
    char *str = "abacab";
    char *ans = longestPalindrome(str);
    printf("%s\n", ans);
    return 0;
}
